package com.zj.leetcode.medium;

/**
 * @program: algorithm
 * @description: 删除链表的倒数第 N 个结点
 * 19 remove-nth-node-from-end-of-list
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class RemoveNthNodeFromEndOfList {
    public static void main(String[] args) {
        Solution solution = new RemoveNthNodeFromEndOfList().new Solution();

        ListNode head = new ListNode(1,
                new ListNode(2,
                        new ListNode(3,
                                new ListNode(4,
                                        new ListNode(5, null)))));

//        System.out.println(solution.size(head));
        System.out.println(solution.removeNthFromEnd(head, 2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }


    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            int size = (int) this.size(head);
            if (size <= 1) {
                return null;
            }
            ListNode temp = head;
            int i = 0;
            int num = size - n - 1;

            do {
                if (i == num) {
                    if (temp.next.next == null) {
                        temp.next = null;
                    } else {
                        temp.next.val = temp.next.next.val;
                        temp.next.next = temp.next.next.next;
                    }
                    return head;
                }

                if (num == -1) {
                    head.val = head.next.val;
                    head.next = head.next.next;
                    return head;
                }

                temp = temp.next;
                i++;

            } while (temp != null);

            return head;
        }

        public long size(ListNode head) {
            long size = 1;
            if (head == null) {
                return 0;
            }
            while (head.next != null) {
                ++size;
                head = head.next;
            }
            return size;
        }

        public void del(ListNode node) {
            if (node.next == null) {
                node.next = null;
                return;
            }
            node.val = node.next.val;
            node.next = node.next.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

